GridKit ヤジリン手筋ソルバーの使用手筋
先行研究
近い記事
橋をかけろ
ソルバーを作る時にどのように手筋を実装しているかという話が手筋集として役に立つことがある。
多くのパズル種は体系だった手筋集が存在しないことも多く、
「初心者が参考にできる唯一の手筋集がソルバーの解説」ということもある。
ヤジリンは手筋集が存在し、GridKitの実装も概ねこの手筋集をもとに実装されている。
記事中での手筋を表す用語も上記記事のものを用いる
そのため、以下の記事は、
手筋集としての役目は果たさないが、
プログラムとして記述する際に
手筋をどう判定しているのか、どうグルーピングしているか
どんなデータ構造を用いてまとめているのか、アルゴリズムを用いているのか。
の参考になるよう記載する。
↑この記事でもヤジリンの基本手筋の体系化について述べている。
また、実際の実装だけでなく、未実装項目、実装予定項目についても述べる。
実績
青い厚揚げさんの毎日出題のヤジリン1308問を98秒掛けて
手筋＋一手仮定で
1287問(98.3%)を求解、21問が解けず。
解けなかった問題の一覧
未実装の分割充填と本数定理が半々
https://scrapbox.io/files/63b1420ab1f905001d141070.png
基本概念
未確定マス
禁止マス
進入不可
矢印付き数字による黒マス充填
対応手筋
1つ飛ばしの黒
黒マスまだないの黒
2n in nの充填(一部)
対象範囲の確認
https://scrapbox.io/files/63b13e4836a5b6001e3b4800.png
濃灰、・は確定
次に同方向矢印が現れるまでの範囲を対象とし、
次に現れる同方向矢印の数字を引いたものを範囲内の黒マスの数とする。
さらに連続する未確定マスで区切って配列とし、
確定している黒マスの数も引く
図の場合
青い部分が 1 in (1x1,1x1)
黄色の部分が2 in (1x4)
となる。
充填手筋適用判定
「連続する未確定マス」の長さをnとすると、その範囲には$ \lfloor\frac{n+1}{2}\rfloor 個の黒マスが入る。
各未確定マスの連続部分に対して、入れることのできる黒マスを合計したものが範囲内に入る黒マスの数、となる。
「入れるべき黒マスの数」が「範囲内に入る黒マスの数」に等しい時、充填手筋が適用できる。
「連続する未確定マス」の各部分について2種類の充填手筋を適用する。
n in 2n-1充填
1つ飛ばしの黒手筋
範囲を0-indexで順に0番目,1番目...と並べる時、偶数番目のマスに黒マスを配置
n in 2n充填
https://scrapbox.io/files/63b147a4fa9cc9001e4f4d5d.png
まず図の×が確定する。
n in 2n の手前の白
適用範囲の両側の端のマスに線が進入不可の時、
範囲の、矢印の示す方向に垂直方向の隣のマス（図の緑のマス）が白マスに確定する。
https://scrapbox.io/files/63b14d98fcc3b0001d5895d2.png
両端から数えて１マス目にあるため、n in 2n の手前の白と呼ぶことにする。
n in 2n の奥の白
両端の先のマスに
https://scrapbox.io/files/63b15363bad895001d29bcf6.png
1*2充填
いずれにせよ
未実装
矢印同士が向き合っている時のヒント引き算
逆方向矢印による範囲でも一方が他方を包含することがあるが未実装
2*nの充填
矢印 数字による白マス確定 (ホワイトニング)
対応手筋
0の白
黒マスもうあるの白
ヒント引き算
同方向の数字付き矢印が現れるまでの区間に存在する黒マスの数が
ヒント引き算行った後の数字と同じであれば、未確定マスをすべて白マスとする